package com.example.system.class22;

/**
 * @Date 2022/8/21
 * @Author Jonathan
 */
public class Code03_CoinChange {
    public static void main(String[] args) {
        System.out.println(ways(new int[]{1, 2, 5}, 6));
    }


    /**
     * @param coins 面值数组 张数是不限量的
     * @param aim   待凑齐的面额
     */
    public static int ways(int[] coins, int aim) {
        return process(coins, 0, aim);
    }


    public static int process(int[] coins, int index, int rest) {
        if (index == coins.length) {
            return rest == 0 ? 1 : 0;
        }

        int ans = 0;
        // 枚举张数 注意边界条件
        // 其实还是枚举所有的情况  暴力递归
        for (int zhang = 0; zhang * coins[index] <= rest; zhang++) {
            ans += process(coins, index + 1, rest - coins[index] * zhang);
        }
        return ans;

    }
}
